package validPalindrome;

/**
 * @author ffzs
 * @describe 680. 验证回文字符串 Ⅱ
 * 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
 *
 * 示例 1:
 *
 * 输入: "aba"
 * 输出: True
 * 示例 2:
 *
 * 输入: "abca"
 * 输出: True
 * 解释: 你可以删除c字符。
 * 注意:
 *
 * 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
 * @date 2020/5/19
 */
public class validPalindrome {
    static boolean canSkip = true;
    public static boolean validPalindrome(String s) {
        int left=0, right=s.length()-1;
        while (left < right){
            if(s.charAt(left)!=s.charAt(right)){
                return delOne(s, left, right);
            }
            left++;
            right--;
        }
        return true;
    }

    public static boolean delOne(String s, int left, int right){
        if(canSkip) canSkip=false;
        else return false;
        return validPalindrome(s.substring(left+1, right+1)) || validPalindrome(s.substring(left,right));
    }


    public static void main(String[] args) {
        String s = "aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga";
        System.out.println(validPalindrome(s));
    }
}
